package fun.coding.leetcode;

public class JumpGame {

	public static void main(String[] args) {
		JumpGame ins = new JumpGame();
		
		int[] test1 = {2, 3, 1, 1, 4};
		System.out.println(ins.canJump(test1));
		
		int[] test2 = {3, 2, 1, 0, 4};
		System.out.println(ins.canJump(test2));
	}
	
	/**
	 *  A = [2,3,1,1,4], return true.
		A = [3,2,1,0,4], return false.
	 */
	// This is a typical DP solution, one thing to optimize is if a point can be reached, all the previous must can be reached. 
	public boolean canJump(int[] A) {
		if (A == null || A.length == 0) return false;
		
		boolean[] lookup = new boolean[A.length];
		lookup[0] = true;
		
		for (int i = 1; i < A.length; i++) {
			for (int j = i - 1; j >= 0; j--) {
				if (lookup[j] && A[j] >= i - j) {
					lookup[i] = true;
					break;
				}
			}
		}
		
		return lookup[A.length - 1];
	}
	/* this is a greedy solution
	class Solution {
		public:
		    bool canJump(int A[], int n) {
		        int reach = 0;
		        for (int i = 0; i <= reach && reach < n; i++) {
		            reach = max (reach, A[i] + i);
		        }
		        
		        return reach;
		    }
		};
		*/
}
